class Solution {
    public int strStr(String haystack, String needle) {
        return byRabinKarp(haystack, needle);
    }
    private int byForce(String s, String t) {
        if (t.length() == 0) return 0;
        if (t.length() > s.length()) return -1;
        for (int i = t.length(); i <= s.length(); i++) {
            if (s.substring(i - t.length(), i).equals(t)) {
                return i - t.length();
            }
        }
        return -1;
    }
    private int byRabinKarp(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        if (needle.length() > haystack.length()) return -1;
        int n = haystack.length();
        int m = needle.length();
        s = " " + haystack;
        hash = new long[n + 1];
        // step = new long[n + 1];
        step = 1L;
        for (int i = 0; i < m; i++) step = step * b % p;
        long hashT = 0L;
        for (int i = 0; i < needle.length(); i++) {
            hashT = (hashT * b + (needle.charAt(i) - 'a' + 1)) % p;
        }
        preGetHash();
        for (int i = m; i < s.length(); i++) {
            if (getSubHash(i - m + 1, i) == hashT 
                && s.substring(i - m + 1, i + 1).equals(needle)) {
                return i - needle.length();
            }
        }
        return -1;
    }
    private long getSubHash(int left, int right) {
        // return ((hash[right] - hash[left - 1] * step[right - left + 1]) % p + p) % p;
        return ((hash[right] - hash[left - 1] * step) % p + p) % p;
    }
    private void preGetHash() {
        hash[0] = 0;
        // step[0] = 1;
        for (int i = 1; i < s.length(); i++) {
            hash[i] = (hash[i-1] * b + s.charAt(i) - 'a' + 1) % p;
            // step[i] = step[i-1] * b % p;
        }
    }
    private static final int b = 131;
    private static final int p = (int)1e9 + 7;
    private long[] hash;
    // private long[] step;
    private long step;
    private String s;
}
